1. Field of the Invention
The present invention relates to a block substitution method of a cache memory in a multiprocessor system including a plurality of processors having cache memories.
2. Related Background Art
In a prior art, when a block-to be substituted in a block substitution of a cache memory (hereinafter referred to as a cache) is to be selected, a block which has a lowest possibility of being referred to in a subsequent program execution is selected in view of the localization of reference which is a common characteristic in the program execution. Specifically, an LRU (least recently used) system in which a block among candidate blocks for substitution which has not been referred to for a longest period is selected, or a FIFO (first-in first-out) system in which a block which has been stored at an oldest time is used.
In addition to the selection system (FIFO, LRU, etc. ) for the block to be selected in the block substitution, a copy back system in which only data in the cache is updated when a CPU write instruction is issued and a main memory is not updated until updating is needed, that is, until a block which contains the data in the cache is selected for the substitution is used rather than a write through system in which the data in the cache and the data in the main memory are simultaneously updated when the CPU write instruction is issued because it is a sole purpose of the cache to promptly execute a service to a main memory access request of the CPU in a single processor system.
It may be said that the cache has been developed and progressed in the single processor system.
However, since the prior art system is a control system based on the localization of reference, the following problem arises in a multiprocessor system (hereinafter referred to as a system) in which a plurality of processors operate in parallel, for example, a plurality of processors and main memories are coupled through a single bus and a cache is provided in each of the processors.
Data integrity among the caches of the respective processors and between the caches and the main memories must be taken into consideration. When the system uses the copy back system to update the main memory when the CPU write instruction is issued, there occurs inconsistency of data content between the cache and the main memory because the written data is not instantly reflected to the main memory. A block which contains such data is called a dirty block. The write back of the dirty block to the main memory (to restore the data integrity between the main memory and the cache) is effected at the following two timings.
(1) When a cache miss to the block in another processor takes place.
(2) When the block is selected as a block to be substituted in the block substitution system.
In those cases, a bus access is required for the write-back to the main memory. The write-back (1) is an effective bus access in that the data is used in the processor which has caused the cache miss, but the write-back (2) is not an effective bus access in the sense of the effective utilization of data.
Further, in a combination of (1) and (2), that is, when a cache miss to a dirty block takes place in a processor immediately after the block has been written back to the main memory by another processor in accordance with a predetermined block substitution system, the bus access takes places twice to the same block at substantially the same time. One of the bus accesses could be avoided if the write-back of the dirty block to the main memory would be delayed for a while. If such a condition frequently occurs, the frequency of bus access increases and a chance of waiting for the bus access rises and a system performance is lowered.